package com.lili.sort;

import java.util.*;

/**
 * @Auther: 李 力
 * @Date: 2024/8/2
 * @Description: 最大间距
 * @version: 1.0
 */
public class LeetCode164 {
    /*
     * 思路: 将数组排序后，遍历数组，找最大的差值
     * 时间复杂度: O(n)
     * 空间复杂度: O(1)
     */
    public int maximumGap(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }
        Arrays.sort(nums);
        int maxNum = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            int a = nums[i];
            int b = nums[i + 1];
            maxNum = Math.max(maxNum, b - a);
        }
        return maxNum;
    }

    //优化如下:采用基数排序
    public int maximumGap2(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }
        //基数排序
        int maxNum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            maxNum = Math.max(maxNum, nums[i]);
        }
        ArrayList<Integer>[] buckets = new ArrayList[10];
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new ArrayList<>();
        }
        int m = 1;
        while (m <= maxNum) {
            for (int num : nums) {
                buckets[num / m % 10].add(num);
            }
            int k = 0;
            for (ArrayList<Integer> bucket : buckets) {
                for (Integer integer : bucket) {
                    nums[k] = integer;
                    k++;
                }
                bucket.clear();
            }
            m = m * 10;
        }

        //寻找差的最大值
        int max = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            int a = nums[i];
            int b = nums[i + 1];
            max = Math.max(max, b - a);
        }
        return max;
    }

}
